package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func pathSum(root *TreeNode, targetSum int) int {
    target := int64(targetSum)
	preSum := map[int64]int{0:1} // preSum -> count
	count := 0
	// cur 是 n 为止的前缀和，不包含 n
	var dfs func(n *TreeNode, cur int64)
	dfs = func(n *TreeNode, cur int64) {
		if n == nil {
			return
		}
		cur += int64(n.Val)
		count += preSum[cur-target]
		preSum[cur]++
		dfs(n.Left, cur)
		dfs(n.Right, cur)
		preSum[cur]--
	}
	dfs(root, 0)
	return count
}

func main() {
	root := 
}